#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k) {
        long long n = arr.size(), sum = 0, mod = 1e9 + 7;
        if (k == 1) {
            long long max = 0, lasti = 0, cur = 0;
            for (int left = 0, right = 0; right < arr.size(); right++) {
                cur += arr[right];
                while (left <= right && cur <= 0)
                    cur -= arr[left], left++;
                if (max < cur)
                    max = cur, lasti = right;
            }
            return max;
        }
        for (int i = 0; i < n; i++)
            sum += arr[i], arr.push_back(arr[i]);
        long long max = 0, lasti = 0, cur = 0;
        for (int left = 0, right = 0; right < arr.size(); right++) {
            cur += arr[right];
            while (left <= right && cur <= 0)
                cur -= arr[left], left++;
            if (max < cur)
                max = cur, lasti = right;
        }
        if (sum > 0) return (max + sum * (k - 2)) % mod;
        else return max % mod;
    }
};